home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 347_01 / tavltree.doc < prev    next >
Text File  |  1991-10-17  |  17KB  |  413 lines
  1. /*:file:version:date: "%n    V.%v;  %f"
  2.  * "TAVLTREE.DOC    V.3;  18-Feb-91,15:23:10"
  3.  *
  4.  *  Purpose: Documentation for TAVL library.
  5.  *
  6.  *      Copyright (c) 1991  Bert C. Hughes
  7.  *                          200 N.Saratoga
  8.  *                          St.Paul, MN 55104
  9.  *                          Compuserve 71211,577
  10.  */
  11.  
  12.  
  13.             ------------------------------------------------
  14.             TAVL library public functions, types & constants
  15.             ------------------------------------------------
  16.  
  17.                             ---------
  18.                             CONSTANTS
  19.                             ---------
  20.  
  21.      - Can be used as parameters for function tavl_insert -
  22. REPLACE ........ 1
  23. NO_REPLACE ..... 0
  24.  
  25.      - Return values of function tavl_setdata -
  26. TAVL_OK ........ 0  No error.
  27. TAVL_NOMEM ..... 1  Out of memory error.
  28. TAVL_ILLEGAL_OP  2  Requested operation would disrupt the
  29.                     tavl_tree structure; operation cancelled.
  30.  
  31.                                -----
  32.                                TYPES
  33.                                -----
  34.  
  35. TAVL_treeptr        Pointer to a TAVL tree.  Most tavl library
  36.                     functions require a TAVL_tree pointer as the
  37.                     first parameter.  A valid TAVL_treeptr can
  38.                     only be obtained via the function "tavl_init",
  39.                     which returns a TAVL_treeptr which can then be
  40.                     used as a parameter for other TAVL functions.
  41.                     All fields in *TAVL_treeptr are absolutely,
  42.                     unequivocally PRIVATE.  No point in even
  43.                     reading them.
  44.  
  45. TAVL_nodeptr        Pointer to a TAVL tree node.  Many TAVL functions
  46.                     require a TAVL_nodeptr as parameter, or return a
  47.                     TAVL_nodeptr.  Fields within *TAVL_nodeptr are
  48.                     PRIVATE - with one possible, but unnecessary,
  49.                     exception: TAVL_nodeptr->dataptr - in which case
  50.                     it is READONLY.
  51.                         Data should be obtained from a TAVL_nodeptr
  52.                     via the function "tavl_getdata", rather than
  53.                     reading "dataptr" directly.
  54.  
  55.  
  56.                         -----------------
  57.                             FUNCTIONS
  58.                         -----------------
  59.  
  60. TAVL_INIT
  61. ---------
  62.     purpose:        Creates a new TAVL tree. Returned pointer is used
  63.                     as a parameter to TAVL routines in subsequent
  64.                     processing.
  65.  
  66.     source file:    tavlinit.c
  67.     returns:        pointer to empty tree, or NULL if
  68.                     insufficient memory.
  69.  
  70.     prototype:      TAVL_treeptr tavl_init(
  71.                             int (*compare)(void *Key1, void *Key2),
  72.                             void *(*key_of)(void *DataObject),
  73.                             void *(*make_item)(const void *DataObject),
  74.                             void (*free_item)(void *DataObject),
  75.                             void *(*copy_item)(void *Dest_DataObject,
  76.                                          const void *Source_DataObject),
  77.                             void *(*alloc)(size_t),
  78.                             void (*dealloc)(void *)
  79.                     );
  80.  
  81.     parameters: All parameters for tavl_init are pointers to functions,
  82.                 so that you can tailor the behavior of the tavltree and
  83.                 the data it stores to fit the needs of your application.
  84.  
  85.                 compare   - Exclusively defines how the tavl library will
  86.                             make comparisons for this tree.
  87.                               must return:
  88.                                         0 - (Key1 == Key2)
  89.                                        >0 - (Key1 > Key2)
  90.                                        <0 - (Key1 < Key2)
  91.  
  92.                 key_of    - Must return a pointer to the identifier of
  93.                             data objects which are being inserted into
  94.                             this instance of tavl tree. Within the TAVL
  95.                             library, result of the "key_of" function is
  96.                             passed directly to the "compare" function.
  97.  
  98.                             (Identifier - that which distinguishes this
  99.                             data object from other data objects.
  100.                             Its "name".)
  101.  
  102.                 make_item - Must create a copy of the data object passed
  103.                             to it. This function is also responsible for
  104.                             allocating memory necessary for storing the
  105.                             copy of the data object.  Library function
  106.                             tavl_insert uses "make_item" to make a copy
  107.                             of the item, or object, to insert into the
  108.                             tree, and library function tavl_setdata uses
  109.                             "make_item" to create a copy of the data
  110.                             item passed to it.
  111.  
  112.                 free_item - Opposite of make_item. Function "free_item"
  113.                             must free or deallocate memory given to
  114.                             the object by "make_item".
  115.  
  116.                 copy_item - Copies a data object to a buffer.  All memory
  117.                             necessary to store the object must have been
  118.                             allocated before "copy_item" is called.
  119.  
  120.                 alloc     - A memory allocator for the tavl library to
  121.                             use for its private purposes, ie, allocation
  122.                             of nodes and struct tavltree.
  123.  
  124.                 dealloc   - Counterpart to "alloc".
  125.  
  126.                   Often "alloc" & "dealloc" will be the complementary
  127.                   C library functions "malloc" and "free".
  128.  
  129.  
  130.  
  131. TAVL_INSERT
  132. -----------
  133.    purpose:     Inserts data objects into the tree.
  134.  
  135.    source file: tavl_ins.c
  136.  
  137.    returns:     A pointer to the node which contains the data object
  138.                 inserted or found.
  139.  
  140.    prototype:   TAVL_nodeptr tavl_insert(
  141.                                 TAVL_treeptr tree,
  142.                                 void        *item,
  143.                                 int          replace
  144.                                 );
  145.  
  146.    parameters:  tree -      Pointer to the tree into which data will be
  147.                             inserted.
  148.  
  149.                 item -      Pointer to the object to insert.
  150.  
  151.                 replace -   Instructs "tavl_insert" on how to behave
  152.                             if the tree already contains a data object
  153.                             whose identifier equals key_of(item).
  154.                             If replace != 0, the new data object will
  155.                             replace the old, otherwise nothing happens,
  156.                             tavl_insert simply returns a pointer to
  157.                             the found node.
  158.  
  159.     NOTES:      "tavl_insert" requires the private function
  160.                 "rebalance_tavl" contained in source file "tavlrebl.c",
  161.                 so the module "tavlrebl.obj" (or whatever, depending on
  162.                 your system) must be linked to the final executable
  163.                 program.
  164.  
  165.  
  166. TAVL_DELETE
  167. -----------
  168.     purpose:        Deletes node containing item such that
  169.                     *key_of(node.item) == *key.
  170.  
  171.     source file:    tavl_del.c
  172.  
  173.     returns:        1 if successful, otherwise 0.
  174.  
  175.     prototype:      int tavl_delete(TAVL_treeptr tree, void *key);
  176.  
  177.     parameters:     tree -  Tree to remove object from.
  178.                     key  -  Identifier of object to remove.
  179.  
  180.     NOTES:      "tavl_delete" requires the private function
  181.                 "rebalance_tavl" contained in source file "tavlrebl.c",
  182.                 so the module "tavlrebl.obj" (or whatever, depending on
  183.                 your system) must be linked to the final executable
  184.                 program.
  185.  
  186.  
  187.  
  188. TAVL_FIND
  189. ---------
  190.     purpose:        Find node whose data object's identifier
  191.                     equals *key.
  192.  
  193.     source file:    tavlfind.c
  194.  
  195.     prototype:      TAVL_nodeptr tavl_